package linkedlist;



import java.util.ArrayList;

public class CircleSingleLinkedListDemo {
    public static void main(String[] args) {
        CircleSingleLinkedList list = new CircleSingleLinkedList();
        ArrayList<Node> arrayList = list.joseph(20, 3);
        for(Node node: arrayList){
            System.out.println(node);
        }
    }

}
class CircleSingleLinkedList{
    private Node first = new Node(0);
    private Node temp;
    private Node cur;

    public CircleSingleLinkedList() {
        //初始化头结点,让其指向自己
        first.next=first;
        temp=cur=first;
    }

    public void add(int num){
        //一次性添加num个节点
        for (int i = 1; i <num ; i++) {
            Node node = new Node(i);
            cur=node;
            temp.next=cur;
            cur.next=first;
            temp=temp.next;
        }
    }
    public ArrayList<Node> joseph(int num,int step){
        Node temp=first;
        Node helperTemp=first;
        Node helper;

        ArrayList<Node> arrayList = new ArrayList<>();
        //创造一个具有num个节点的单项环形链表
        add(num);
        //将helper指向最后一个节点
        while(helperTemp.next!=first){
            helperTemp=helperTemp.next;
        }
        helper=helperTemp;
        //约瑟夫问题
        while (temp.next!=temp){
            for (int i = 0; i <step-1 ; i++) {
                temp=temp.next;
                helper=helper.next;
            }
            arrayList.add(temp);
            temp=temp.next;
            helper.next=temp;
        }
        arrayList.add(temp);
       return arrayList;
    }
    public void show(){
        Node temp=first;
        if (first==null){
            System.out.println("链表为空");
            return;
        }
        //先将第一个节点输出
        while(temp.next!=first){
            System.out.println(temp);
            temp=temp.next;
        }
    }
}
class Node{
    int no;
    Node next;

    public Node(int no) {
        this.no = no;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                '}';
    }
}